package pub.dsb.example.algorithm;

/**
 * <p>
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 * </p>
 *
 * @author Yi
 * @version V1.0.0
 * @date 2021/1/6 11:24
 * @modificationHistory=========================逻辑或功能性重大变更记录
 * @modify By: {修改人} 2021/1/6 11:24
 * @modify reason: {方法名}:{原因}
 * ...
 * @since V1.0.0
 */
public class LC5Test {
    public static void main(String[] args) {
        System.out.println(new Solution20200106().longestPalindrome("abcsdscbe"));
        System.out.println(new Solution20200106().longestPalindrome("babad"));
        System.out.println(new Solution20200106().longestPalindrome("a"));
        System.out.println(new Solution20200106().longestPalindrome("aacabdkacaa"));
        System.out.println(new Solution20200106().longestPalindrome("dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd"));
        System.out.println(new Solution20200106().longestPalindrome("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee"));
    }
}

class Solution20200106 {
    public String longestPalindrome(String s) {
        long t1 = System.currentTimeMillis();
        /*
        abcdcbe
        abcdcbe -> 无 a
        bcdcbe -> 有b
               -> 判断是否有 bc 的反转字符串 cb
                -> 有cb
                -> 计算 bc 的下标和 cb 的下标之差是否大于0
                    -> 等于0或1，跳出循环
                    -> 大于1，循环上述步骤
        方式2：
        -> 反转字符串： ebcdcbca
        -> 逐位比较，记录偏移

        bcabad
        dabacb

        aaca bdkacaa 0,4
        aaca kdbacaa 0,4

        a aca bdkacaa 1,3
        aacakdb aca a 7,9  10-7 = 3 10-9 = 1
         */
        String revStr = "";
        for (int i = s.length() - 1; i >= 0; i--) {
            revStr += String.valueOf(s.charAt(i));
        }
        // 寻找最大重复子串
        int pos = 0, max = 0;
        int start = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            pos = i;
            while (n > pos
                    && revStr.contains(s.substring(i, ++pos))
            ) {
                if (pos - i > max &&
                        s.substring(i, pos)
                                .equals(revStr.substring(n-pos,n-i))
                ) {
                    max = pos - i;
                    start = i;
                }
            }
        }
        System.out.println("t2:" + (System.currentTimeMillis() - t1));
        System.out.println("s1:" + revStr);
        System.out.println("s2:" + s.substring(start, start + max));
        return s.substring(start, start + max);
    }
}
